package leetcode每日一题;

/**
 * 1. 问题描述
 *      如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。
 *      第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。
 *      例如，[1,7,4,9,2,5] 是一个摆动序列，因为差值 (6,-3,5,-7,3)是正负交替出现的。
 *      相反, [1,4,7,2,5]和[1,7,4,5,5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，
 *      第二个序列是因为它的最后一个差值为零。
 *      给定一个整数序列，返回作为摆动序列的最长子序列的长度。
 *      通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。
 *
 * 2. 算法分析
 *      分析题意
 *          题目要求是人给一个序列，我们需要找到这个序列的最长摇摆子序列的长度
 *          所谓的摇摆序列为x, 若x满足：
 *              (x[i]-x[i-1])(x[i+1]-x[i]) < 0
 *          具体的例子：
 *              [1,4,2,3]   [4,2,3,1]
 *                + - +       - + -
 *          实际上通过上述例子我们可以看出摇摆序列大致上可以分成两类：
 *              第一类：最后的符号差为 + ，我们称为升序摇摆序列
 *              第二类：最后的符号差为 - ，我们称为降序摇摆序列
 *
 *      算法分析
 *          题目要求我们找到最长的摇摆序列，类似于最长公共子序列，我们很快可以联想到使用动态规划的算法实现
 *          如果使用一个dp数组来求解此问题会显得有些困难，注意到上述的分类，我们设置两个数组up,down数组，
 *          其中up[i]：nums[0:i]的最长升序摇摆子序列, down[i]：nums[0:i]的最长降序摇摆子序列，实际
 *          上两个数组分别记录了这个数组的最大升序摇摆子序列和最大降序摇摆子序列，最终返回最长的一个即可
 *
 *          局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值。
 *          整体最优：整个序列有最多的局部峰值，从而达到最长摆动序列。
 *
 *          具体分析如下：
 *             首先由题意可知，up[0] = down[0] = 1,下面我们分类讨论上述问题：
 *             分成nums[i+1] > nums[i] 或者 nums[i+1] - nums[i] < 0
 *             当nums[i+1] > nums[i]时：
 *                   1. 当down[i]以nums[i-1]结尾
 *                      此时我们显然有 up[i+1] = down[i] + 1
 *                   2. 当down[i]以nums[j]结尾，其中 j < i-1
 *                      此时我们任然有 up[i+1] = down[i] + 1
 *                      Proof:
 *                          有down的定义可知 nums[j:i]之间不存在 + -这样符号差序列，否则
 *                          于down的最大性值矛盾，所以up[i+1] = down[i] + 1
 *
 *             当nums[i+1] < nums[i]时：
 *                   分析同上
 *
 *             当nums[i+1] = nums[i]时：
 *                   当前后两个数相同的时候，nums[0:i]于nums[0:i+1]的down和up一样
 *                   所以可以忽略这种情况
 *          伪代码：
 *              up = 1; down = 1
 *              if(nums[i] > nums[i-1]) {
 *                  up = down + 1;
 *              }
 *              if(nums[i] < nums[i-1]) {
 *                  down = up + 1;
 *              }
 *
 *
 *      leetcode上的一些其他的解法：
 *
 *
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 最长摇摆子序列 {
    public static void main(String[] args) {

    }

    public static int wiggleMaxLength(int[] nums) {
        int up = 1; // 记录上升的最长摇摆序列的长度
        int down = 1; // 记录下降的最长摇摆序列的长度
        for(int i = 1; i < nums.length; i++) {
            if(nums[i] > nums[i-1]) {
                up = down + 1;
            } else if(nums[i] < nums[i-1]){
                down = up + 1;
            }
        }
        return (nums.length == 0) ? 0 : Math.max(up,down);
    }


    /**
     * 贪心算法
     * 我们将数组中的所有数字按照大小关系上下的摆放，类似于一个起伏的山峰
     * 具体的例子：[1,17,5,10,13,15,10,5,16,8]
     *     17
     *                                   16
     *                      15
     *                  13
     *              10           10
     *                                         8
     *          5                    5
     *
     *  1
     *  注意到这个序列有三个峰值，将整个数组划分为6条山路，如果山顶于山脚之间有元素，说明之间的这些元素
     *  时单调的，删除即可，最终将所有这样的元素删除就是最长摇摆序列了
     *
     *  将上述转化为代码逻辑：
     *      找到数组所有的单调子区间，删除不包含边界的内点元素，最后就是
     *      整个题目转化为找单调区间
     *      实际操作上，其实连删除的操作都不用做，因为题目要求的是最长摆动子序列的长度，
     *      所以只需要统计数组的峰值数量就可以了（相当于是删除单一坡度上的节点，然后统计长度）
     *      这就是贪心所贪的地方，让峰值尽可能的保持峰值，然后删除单一坡度上的节点。
     * @param nums
     * @return
     */
    public static int wiggleMaxLength2(int[] nums) {
        if (nums.length <= 1) return nums.length;
        int curDiff = 0; // 当前一对差值
        int preDiff = 0; // 前一对差值
        int result = 1;  // 记录峰值个数，序列默认序列最右边有一个峰值
        for (int i = 1; i < nums.length; i++) {
            curDiff = nums[i] - nums[i - 1];
            // 出现峰值
            if ((curDiff > 0 && preDiff <= 0) || (preDiff >= 0 && curDiff < 0)) {
                result++;
                preDiff = curDiff;
            }
        }
        return result;
    }
}
